AtCoder Beginner Contest 277 G
（工事中）
解き方
二項定理を利用するため、この記事においては$ 0^{0} = 1 とする。
頂点全体の集合を$ V とし、頂点$ v に隣接している頂点全体の集合を$ E(v) とする。
また、頂点$ v のうち、$ C_{v} = 0 を満たす頂点全体の集合と、$ C_{v} = 1 を満たす頂点全体の集合をそれぞれ$ V_{0} 、$ V_{1} とする。
まずは答えを求める方法について述べ、その後にその方法の正当性について述べる。
答えを求めるために、以下のような漸化式で定められる2つの関数$ \mathrm{dp}_{1} と$ \mathrm{dp}_{2} を考える。
$ \mathrm{dp}_{1} (1, 1, 0) = 1 かつ、$ 1 以外の任意の頂点$ v \in V \setminus \{ 1 \} について$ \mathrm{dp}_{1} (1, v, 0) = 0 とする。
任意の正整数$ l と任意の頂点$ v について、$ \mathrm{dp}_{1} (1, v, l) = 0 とする。
頂点$ v \in V_{0} と正整数$ i および非負整数$ l について、$ \mathrm{dp}_{1} (i+1, v, l) = \sum_{v^{\prime} \in E(v)} \frac{1}{|E(v^{\prime})|} \left( \sum_{l^{\prime}=0}^{l} {}_{l} \mathrm{C}_{l^{\prime}} \times \mathrm{dp}_{1} (i, v, l^{\prime}) \right) とする。
頂点$ v \in V_{1} と正整数$ i および非負整数$ l について、$ \mathrm{dp}_{1} (i+1, v, l) = \sum_{v^{\prime} \in E(v)} \frac{1}{|E(v^{\prime})|} \mathrm{dp}_{1} (i, v, l) とする。
任意の頂点$ v \in V_{0} について$ \mathrm{dp}_{2} (K+1, v) = 0 とする。
任意の頂点$ v \in V_{1} について$ \mathrm{dp}_{2} (K+1, v) = 1 とする。
任意の頂点$ v \in V_{0} と$ K 以下の正整数$ i について$ \mathrm{dp}_{2} (i, v) = \frac{1}{|E(v)|} \sum_{v^{\prime} \in E(v) \cap V_{1}} \mathrm{dp}_{2} (i+1, v^{\prime}) とする。
任意の頂点$ v \in V_{1} と$ K 以下の正整数$ i について$ \mathrm{dp}_{2} (i, v) = 1+\frac{1}{|E(v)|} \sum_{v^{\prime} \in E(v) \cap V_{1}} \mathrm{dp}_{2} (i+1, v^{\prime}) とする。
正整数$ i と頂点$ v について、確率変数$ X_{i,v} と確率変数$ Y_{i,v} の値を次のように定める。
$ i 回目の行動の直前に$ v にいるときは、その時のレベルが確率変数$ X_{i,v} の値となる。
$ i 回目の行動の直前に$ v にいない場合は、$ 0 が確率変数$ X_{i,v} の値となる。
$ i 回目の行動の直前に$ v にいるときは、次にレベルが上がるか$ K 回の行動が終わるまでにお金を獲得する回数が$ Y_{i,v} の値となる。
$ i 回目の行動の直前に$ v にいない場合は、$ 0 が確率変数$ Y_{i,v} の値となる。
$ C_{v} = 1 となる頂点に移動したときはレベルが上がらないため、レベルが$ X の状態で$ C_{v} = 1 となる頂点に$ Y 回移動したとき、高橋くんは$ X^{2}Y 円を獲得する。
よって、レベルが上がった場所と時間でで場合分けすることを考えると、求める期待値は$ \mathbf{E} \left( \sum_{i=1}^{K} \sum_{v \in V \land C_{v} = 1} X_{i,v}^{2} (Y_{i,v}-1) \right) となる。
ここで、$ i 回目の行動の直前に$ v にいるときに$ 1 、それ以外の場合に$ 0 となる確率変数$ I_{i,v} を考える。
$ I_{i,v} = 1 となる場合、$ X_{i,v} は$ i 回目より前の行動のみによって決まり、$ Y_{i,v} は$ i 回目以降の行動のみによって決まる。
この問題において各回の行動は、そのときにいる頂点によってのみ決まる（つまりマルコフ連鎖である。）
よって、$ I_{i,v} = 1 という条件のもとでは$ X_{i,v} と$ Y_{i,v} は独立とみなせるので、次の式が成り立つ。
ただし$ \mathbf{E} (X \mid I_{i,v}=1) は、$ I_{i,v} = 1 という条件における$ X の条件付き期待値を表すとする。
$ \mathbf{E} ( X_{i,v}^{2} (Y_{i,v}-1) \mid I_{i,v}=1) = \mathbf{E} ( X_{i,v}^{2} \mid I_{i,v}=1)\mathbf{E} (Y_{i,v}-1 \mid I_{i,v}=1)
また、$ I_{i,v} = 0 のときは、$ X_{i,v} = Y_{i,v} = 0 であるため、$ \mathbf{E} ( X_{i,v}^{2} (Y_{i,v}-1) \mid I_{i,v}=0) = 0 となる。
以上の事実と、期待値の線型性から、求める期待値は下のようになる。
$ \sum_{i=1}^{K} \sum_{v \in V \land C_{v} = 1} \mathbf{P} (I_{i,v} = 1) \mathbf{E}(X_{i,v}^{2} \mid I_{i,v}=1) \mathbf{E} (Y_{i,v}-1 \mid I_{i,v} = 1) = \sum_{i=1}^{K} \sum_{v \in V \land C_{v} = 1} \mathbf{E}(X_{i,v}^{2}) \mathbf{E} (Y_{i,v}-1 \mid I_{i,v} = 1)